package com.lzq.leetcode.bat;

import java.util.HashMap;
import java.util.Map;

public class MLRUWithTTL {

    static class Node {
        int key;
        int val;
        long ttl;
        Node next;
        Node pre;

        public Node() {}
        public Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }

    static class CacheList {
        Node head, tail;
        int size;

        CacheList() {
            head = new Node();
            tail = new Node();
            head.next = tail;
            tail.pre = head;
            size = 0;
        }

        public void remove(Node node) {
            node.pre.next = node.next;
            node.next.pre = node.pre;
            --size;
        }

        public void addToHead(Node node) {
            node.next = head.next;
            head.next.pre = node;
            node.pre = head;
            head.next = node;
            ++size;
        }

        public Node removeLast() {
            if (size == 0)  return null;
            Node node = tail.pre;
            remove(node);
            return node;
        }
    }

    // 缓存
    private final long ttl;
    private final CacheList cache;
    private final int capacity;
    private final Map<Integer, Node> map;

    MLRUWithTTL(int capacity ,long ttl) {
        this.capacity = capacity;
        this.ttl = ttl;
        this.cache = new CacheList();
        this.map = new HashMap<>();
    }

    public void put(int key, int val) {
        Node node = null;
        if (map.containsKey(key)) {
            node = map.get(key);
            node.val = val;         // 注意更新val
            cache.remove(node);
        } else {
            node = new Node(key, val);
            map.put(key, node);
        }
        node.ttl = System.currentTimeMillis() + ttl;
        cache.addToHead(node);
        // 判断容量
        if (cache.size > capacity) {
            Node last = cache.removeLast();
            if (last != null) map.remove(last.key);
        }
    }

    public int get(int key) {
        if (!map.containsKey(key)) {
            return -1;
        }

        // 判断时间
        Node node = map.get(key);
        if (node.ttl < System.currentTimeMillis()) {
            cache.remove(node);
            map.remove(node.key);
            return -1;
        }
        // 刷新时间
        node.ttl = System.currentTimeMillis() + ttl;
        cache.remove(node);
        cache.addToHead(node);
        return node.val;
    }

    public static void main(String[] args) throws InterruptedException {
        MLRUWithTTL cache = new MLRUWithTTL(2, 2000); // 容量为2，TTL为2秒
        cache.put(1, 100);
        cache.put(2, 200);
        System.out.println(cache.get(1));
        System.out.println(cache.get(2));
        cache.put(4, 400);
        System.out.println(cache.get(1)); // 输出 100
        System.out.println(cache.get(4));
        Thread.sleep(2500); // 等待2.5秒
        System.out.println(cache.get(1)); // 输出 -1（过期）
        cache.put(3, 300);
        System.out.println(cache.get(3)); // 输出 300
    }
}
